Acorn RISC PD-CD 1

home *** CD-ROM | disk | FTP | other *** search

/ Acorn RISC PD-CD 1 / Acorn RISC PD-CD 1.iso / languages / hope / hopetutorl < prev

Wrap

Text File | 1990-04-25 | 53.5 KB | 2,113 lines

A HOPE TUTORIAL Roger Bailey, Imperial College Functions In Conventional Languages: In a language like Pascal, a function is a piece of 'packaged' program for performing standard operations like finding square roots. To obtain the square root of a positive number stored in a variable x, we write: sqrt ( x ) at the point in the program where we want the value, such as: writeln ( 1.0 + sqrt ( x ) ) ; this is called an application of the function. The value represented by "x" is called the argument or actual parameter. In this context, the canned program computes the square root of "x", "1.0" is added to it and the result is then printed. We can also define our own functions specifying how the result is computed using ordinary Pascal statements. Here's a function that returns the greater of its two argument values: function max ( x, y : INTEGER ) : INTEGER ; begin if x > y then max := x else max := y end ; The identifiers "x" and "y" are called formal parameters. They're used inside the definition to name the two values that will be supplied as arguments when the function is applied. We can use "max" anywhere we need a value, just like "sqrt". Here's how we might use "max" to filter out negative values on output: writeln ( max ( z, 0 ) ) ; Hope Tutorial Page 1 A more interesting case is when the actual parameter is a function application itself or involves one. We can use "max" to find the largest of three numbers by writing: max ( a, max ( b, c ) ) Combining functions together like this is called composition. The expression is evaluated 'inside-out' because the outer application of "max" can't be evaluated until the value of its second argument is known. The inner application of "max" is therefore evaluated first using the values of "b" and "c" and the result is used as the actual parameter of the outer application. Another way of combining functions together is to define more powerful ones using simpler ones as 'building blocks'. If we often need to find the largest of three numbers we might define: function MaxOf3 ( x, y, z : INTEGER ) : INTEGER ; begin MaxOf3 := max ( x, max ( y, z ) ) end ; and apply it by writing: MaxOf3 ( a, b, c ) Programming with functions Pascal is called an imperative language because programs written in it are recipes for 'doing something'. If our programs consist only of functions, we can concentrate on what the results are and ignore how they're computed. Forget that "sqrt" is a piece of code and think of "sqrt ( x )" as a way of writing a value in your program, and you'll get the idea. You can think of "MaxOf3" like this as well if you ignore the way it works inside. By defining a 'toolkit' of useful functions and combining them together like this, we can build powerful programs that are quite short and easy to understand. Hope Tutorial Page 2 In Pascal, functions can only return 'simple' data objects such as numbers or characters, but real programs use big data structures and can't easily be written using these functions. In Hope, functions can return any type of value, including data structures equivalent to Pascal's arrays and records and much more. Programming in Hope has the flavour of simply 'writing down the answer' by writing an expression that defines it. This will contain one or more function applications to define smaller parts of the answer. These functions won't usually be built in like "sqrt", so we'll have to define them ourselves, but we'll still think of them as definitions of data objects, and not as algorithms for computing them. A simple Hope example -- conditionals Let's see how we can define "max" in Hope. Like Pascal, it's a strongly-typed language, which means we must tell the compiler about the types of all objects in our programs so it can check that they're used consistently. The function definition comes in two parts. First we declare the argument and result types: dec max : num # num -> num ; "dec" is in bold face because it's a reserved word and you can't use it as a name. Type it in lower case when entering programs. "max" is the name of the function being defined. Names consist of upper and lower case letters (which are distinct) and digits, and must start with a letter. The current fashion is to use lower case. The layout isn't significant and you can separate symbols with any number of blanks, tabs and newlines for clarity, as in this example. Symbols need only be separated when they might otherwise be confused as one, such as "dec" and "max". The next part of the declaration gives the types of the arguments (read the symbol ":" as 'takes a'). Non-negative integers are of the predefined type "num" (in lower case). "#" is read as 'and a'; (or you can use the reserved word "X"). "->" is read as 'yields'. The semicolon marks the end of the declaration, which tells the compiler that "max" takes two numbers as arguments and returns a single number as its result. The result of a function is defined by one or more recursion equations. "max" needs only one equation to define it: --- max ( x, y ) <= if x > y then x else y ; Hope Tutorial Page 3 Read the symbol "---" as 'the value of'. The expression "max ( x, y )" is called the left-hand side of the equation. It defines "x" and "y" as formal parameters, or local names for the values that will be supplied when the function is applied. Parameter names are local to the equation, so "x" and "y" won't be confused with any other "x" or "y" in the program. The symbol "<=" is read as 'is defined as'. The rest of the equation (called the right-hand side) defines the result. It's a conditional expression. The symbols "if", "then" and "else" are reserved words. Pascal's conditional statement chooses between alternative actions, but Hope's conditional expression chooses between alternative values, in line with our view that function applications are ways of writing values rather than recipes for computing them. If the value of the expression "x > y" is "true", the value of the whole conditional expression is the value of "x", otherwise it's the value of "y". The alternative values can be defined by any Hope expressions. When the value of a function is defined by more than one expression like this, they are evaluated in an unspecified order. On a suitable computer, such as the Imperial College ALICE machine, it's even possible to evaluate both expressions and the test in parallel and throw away one of the values according to the result of the test. Using functions that we've defined A Hope program is just a a single expression containing one or more function applications composed together. It's evaluated immediately and the result and its type are printed on the screen. Here's a simple program that uses "max", with its output (which is shown in italics): max ( 10, 20 ) + max ( 1, max ( 2,3 ) ) ; 23 : num The rules for evaluating the expression are the same as those of Pascal: function arguments are evaluated first, the functions are applied, and finally other operations are performed in the usual order of priority. Hope Tutorial Page 4 We can also use existing functions to define new ones. Here's the Hope version of "MaxOf3": dec MaxOf3 : num # num # num -> num ; --- MaxOf3 ( x, y, z ) <= max ( x, max ( y, z ) ) ; A more interesting example - repetition Just as Pascal's conditional statement is replaced by Hope's conditional value, so the repetitive statement is replaced by the repetitive value. Here's a Pascal function that multiplies two numbers using repeated addition: function mult ( x, y : INTEGER ) : INTEGER ; var prod : INTEGER ; begin prod := 0 ; while y > 0 do begin prod := prod + x ; y := y - 1 end ; mult := prod end ; It's hard to be sure this function does enough additions (it took me three tries to get it right) and this seems to be a general problem with loops in programs. A common way of checking imperative programs is to simulate their execution. If we do this for input values of 2 and 3, we'll find that "prod" starts with the value 0 and gets values of 2, 4 and 6 on successive loop iterations, which suggests the definition is correct. Hope Tutorial Page 5 Hope doesn't have any loops, so we must write all the additions that the Pascal program performed in a single expression. It's much easier to see that this has the right number of additions: dec mult : num # num -> num ; --- mult ( x, y ) <= 0 + x + x + ... or would be if we knew how many times to write "+ x". The hand simulation suggests we need to write it "y" times, which is tricky when we don't know the value of "y". What we do know is that for a given value of "y", the expressions: mult ( x, y ) and mult ( x, y-1 ) + x will have the same number of "+ x" terms if written out in full. The second one always has two terms, whatever the value of "y", so we'll use it as the definition of "mult": --- mult ( x, y ) <= mult ( x, y-1 ) + x ; On the face of it we've written something ridiculous, because it means we must apply "mult" to find the value of "mult". Remember however that this is really shorthand for "0" followed by "y" occurrences of "+ x". When "y" is zero, the result of "mult" is also zero because there are no "+ x" terms. In this case "mult" isn't defined in terms of itself, so if we add a special test for it, the definition terminates. A usable definition of "mult" is: --- mult ( x, y ) <= if y = 0 then 0 else mult ( x, y-1 ) + x ; Functions that are defined using themselves like this are called recursive. Every Pascal program using a loop can be expressed as a recursive function in Hope. All recursive definitions need one case (called the base case) where the function isn't defined in terms of itself, just as Pascal loops need a terminating condition. Hope Tutorial Page 6 Another way of using functions Hope allows us to use a function with two arguments like "mult" as an infix operator. We must assign it a priority and use it as an operator everywhere including the equations that definine it. The definition of "mult" when used as an infix operator looks like this: infix mult : 8 ; dec mult : num # num -> num ; --- x mult y <= if y = 0 then 0 else x mult ( y - 1 ) + x ; A bigger number in the infix declaration means a higher priority. The second argument of "mult" is parenthesised because its priority of 8 is greater than the built-in subtraction operation. Most of Hope's standard functions are supplied as infix operators. Other kinds of data Hope provides two other primitive data types. A "truval" (truth value) is equivalent to a Pascal Boolean and has values "true" and "false". We've already seen the expression "x > y" defining a truth value. ">" is a standard function whose type is "num # num -> truval". We can use truth values in conditional expressions and combine them together with the standard functions "and", "or" and "not". Single characters are of type "char", with values "'a'", "'b'" and so on. Characters are most useful as components of data structures such as character-strings. Hope Tutorial Page 7 Data structures Practical programs need data structures and Hope has two standard kinds already built in. The simplest kind corresponds to a Pascal record. We can bind a fixed number of objects of any type together into a structure called a tuple, for example: ( 2, 3 ) or ( 'a', true ) are tuples of type "num # num" and "char # truval" respectively. We use tuples when we want a function to define more than one value. Here's one that defines the time of day given the number of seconds since midnight: dec time24 : num -> num # num # num ; --- time24 ( s ) <= ( s div 3600, s mod 3600 div 60, s mod 3600 mod 60 ) ; "div" is the built-in integer division function and "mod" gives the remainder after integer division. If we type an application of "time24" at the terminal, the result tuple and its type will be printed on the screen in the usual way: time24 ( 45756 ) ; ( 12,42,36 ) : ( num # num # num ) Hope Tutorial Page 8 The second standard data type, called a list, corresponds roughly to a one-dimensional array in Pascal. It can contain any number of objects (including none at all) but they must all be the same type. We can write expressions in our programs that represent lists, such as: [ 1, 2, 3 ] which is of type "list ( num )". There are two standard functions for defining lists. The infix operator "::" (read as 'cons') defines a list in terms of a single object and list containing the same type of object, so 10 :: [ 20, 30, 40 ] defines the list: [ 10, 20, 30, 40 ] Don't think of "::" as adding "10" to the front of "[ 20, 30, 40 ]". It really definines a new list "[ 10, 20, 30, 40 ]" in terms of two other objects without changing their meaning, rather in the same way that "1 + 3" defines a new value of "4" without changing the meaning of "1" or "3". The other standard list function is "nil", which defines a list with no elements in it. We can represent every list by an expression consisting of applications of "::" and "nil". When we write an expression like: [ a + 1, b - 2, c * d ] it's considered to be a shorthand way of writing: a + 1 :: ( b - 2 :: ( c * d :: nil ) ) There's also a shorthand way of writing lists of characters. The following three expressions are all equivalent: "cat" [ 'c', 'a', 't' ] 'c' :: ( 'a' :: ( 't' :: nil ) ) Hope Tutorial Page 9 When the result of a Hope program is a list, it's always printed out in the concise bracketed notation; if it's a list of characters, it's printed in quotes. Every data type in Hope is defined by a set of primitive functions like "::" and "nil". They're called constructor functions, and aren't defined by recursion equations. When we defined a tuple, we were actually using a standard constructor called "," (read as 'comma'). Later on we'll see how constructors are defined for other types of data. Functions that define lists If we wanted to write a Pascal program to print the first n natural numbers in descending order we'd probably write a loop that printed one value out on each iteration, such as: for i := n downto 1 do write ( i ) ; In Hope we write one expression that defines all the values at once, rather like we did for "mult": dec nats : num -> list ( num ) ; --- nats ( n ) <= if n = 0 then nil else n :: nats ( n-1 ) ; "nil" is useful for writing the base case of a recursive function that defines a list. If we try the function at the terminal by typing: nats ( 10 ) ; [ 10,9,8,7,6,5,4,3,2,1 ] : list ( num ) we can see that the numbers are in descending order because that's the way we arranged them in the list, and not because they were defined in that order. The values in the expression defining the list are treated as though they were all generated at the same time. On the ALICE machine they actually are generated at the same time. Hope Tutorial Page 10 To get the results of a Hope program in the right order, we must put them in the right place in the final data structure. If we want the list of the numbers "n" through "1" in the opposite order we can't write the definition as: ... else nats ( n-1 ) :: n ; because the argument types for "::" are the wrong way round. We need to use a another built-in operation "<>" (read as 'append') that concatenates two lists. The definition will then look like this: --- nats ( n ) <= if n = 0 then nil else nats ( n-1 ) <> [ n ] ; We put "n" in brackets to make it into a (single-item) list because "<>" expects both its arguments to be lists. We could also have written "( n :: nil )" instead of "[ n ]". Data structures as parameters Suppose we have a list of integers and we want to write a function to add up all its elements. The declaration will look like this: dec sumlist : list ( num ) -> num ; We need to refer to the individual elements of the actual parameter in the equations defining "sumlist". We do this using an equation whose left-hand side looks like this: --- sumlist ( x :: y ) ... Hope Tutorial Page 11 This is an expression involving list constructors and corresponds to an actual parameter that's a list. "x" and "y" are formal parameters, but they now name individual parts of the actual parameter value. In an application of "sumlist" like: sumlist ( [ 1, 2, 3 ] ) the actual parameter will be 'dismantled' so that "x" names the value "1" and "y" names the value "[ 2, 3 ]". The complete equation will be: --- sumlist ( x :: y ) <= x + sumlist ( y ) ; Notice there's no base case test. As we might expect, it's the empty list, but we can't test for it directly in the equation because there's no formal parameter that refers to the whole list. In fact, if we write the application: sumlist ( nil ) we'll get an error message because we can't dismantle "nil" to find the values of "x" and "y". We must cover this case separately using a second recursion equation: --- sumlist ( nil ) <= 0 ; The two equations can be given in either order. When "sumlist" is applied, the actual parameter is examined to see which constructor function was used to define it. If the actual parameter is a non-empty list, the first equation is used, because non-empty lists are defined using the "::" constructor. The first number in the list gets named "x" and the remaining list "y". If the actual parameter is the empty list, the second equation is be used because empty lists are defined using the constructor "nil". Hope Tutorial Page 12 Pattern-matching An expression composed of constructors appearing on the left-hand side of a recursion equation is called a pattern. Selecting the right recursion equation and dismantling the actual parameter to name its parts is called pattern-matching. When you write a function, you must give a recursion equation for each possible constructor defining the argument type. Sometimes we don't need to dismantle the actual parameter, and we can use a formal parameter in the pattern that matches the whole object, irrespective of what constructors were used to define it. As an example, let's see how we could define our own function to concatenate two lists like the built-in operation "<>": infix cat : 4 ; dec cat : list( num ) # list( num ) -> list ( num ) ; --- ( h :: t ) cat l <= h :: ( t cat l ) ; --- nil cat l <= l ; The first list parameter is matched by the pattern "( h :: t )" so that its first item (the 'head") and the remaining list (the 'tail') can be referred to separately on the right-hand side. The second recursion equation covers the case when the first list is empty. The second list parameter is matched by the pattern "l" whether it's empty or not. As well as writing enough recursion equations to satisfy all the parameter constructors, we must also be careful not to write sets of equations where more than one pattern might match the actual parameters, because that would be ambiguous. We can write patterns to match arguments that are tuples in the same way using the tuple constructor ",". When we wrote "mult ( x, y )" you probably thought the parentheses and the comma were something to do with the function application. In fact, we were constructing a tuple and the parentheses were only needed because "," has a low priority. Hope treats all functions as having only one argument. This can be a tuple when you want the effect of several arguments. Without parentheses, mult x, y would be interpreted as: ( mult ( x ), y ) Hope Tutorial Page 13 A recursion equation with the left-hand side: --- mult ( x, y ) <= ... is just a pattern-match on a tuple. The first item in the tuple gets named "x" and the second one "y". We can also use pattern-matching on "num" parameters. These are defined by two constructors called "succ" and "0". "succ" defines a number in terms of the next lower one. "0" has no arguments and defines the value zero. Surely "0" is a value, not a function? Well, we're already used to thinking of function applications as another way of writing values, so it's quite consistent to think of "0" as a function application. Here's a version of "mult" that uses pattern-matching to identify the base case: infix mult : 8 ; dec mult : num # num -> num ; --- x mult 0 <= 0 ; --- x mult succ ( y ) <= ( x mult y ) + x ; We can read "succ ( y )" as 'the successor of some number that we'll call "y"'. Instead of naming the actual parameter "y" like we did in the original version of "mult", we're naming its predecessor. Hope Tutorial Page 14 Simplifying expressions In Pascal programs we can simplify complex expressions by removing common sub-expressions and evaluating them separately. Instead of: writeln ( ( x + y ) * ( x + y ) ) ; we would probably write: z := x + y ; writeln ( z * z ) ; which is clearer and more efficient. Hope programs consist only of expressions and it's even more important to simplify them. We do this by using a qualified expression: let z == x + y in z * z ; This looks like an assignment, but it isn't. "==" is read as 'is defined as' and "z" is local to the expression following the "in". If we write something like: let z == z + 1 in z * z ; we're actually introducing a new variable "z" to use in the sub-expression "z * z". It hides the original one in the sub-expression "z + 1". There's a second form of qualified expression for people who like to use variables first and define their meanings later. It looks like this: z * z where z == x + y ; The result of the qualified expression is the same whether we define it using let or where. "x + y" is evaluated first, and its value is used in the main expression. Hope Tutorial Page 15 The qualifying expression will often be a function application that defines a data structure. If we want to name part of the structure we can use a pattern on the left-hand side of the "==" symbol: dec time12 : num -> num # num ; --- time12 ( s ) <= ( if h > 12 then h-12 else h, m ) where ( h, m, s ) == time24 ( s ) ; We'll use this construction most often when we write recursive functions that define tuples. Here's a typical example. Suppose we want to form a string of words from a sentence. For simplicity a word is taken to be any sequence of characters, and words are separated in the sentence by any number of blanks. The sentence and a single word will be of type "list ( char )" and the final sequence of words a "list ( list ( char ) )". It's fairly straightforward to obtain the first word. Here's a function that does it: dec firsttry : list ( char ) -> list ( char ) ; --- firsttry ( nil ) <= nil ; --- firsttry ( c :: s ) <= if c = ' ' then nil else c :: firsttry ( s ) ; One of the nice features of Hope is that we can type in and print out any kind of value, so it's easy to check out the individual functions of our program separately. If we test "firsttry" we'll see: firsttry ( "You may hunt it with forks and Hope" ) ; "You" : list ( char ) But there's a problem here because we're going to need the rest of the sentence if we're to find the remaining words. We must arrange that that the function returns the remaining list as well as the first word. This is where tuples come in: dec firstword : list ( char ) -> list ( char ) # list ( char ) ; --- firstword ( nil ) <= ( nil, nil ) ; --- firstword ( c :: s ) <= if c = ' ' then ( nil, s ) else ( ( c :: w, r ) where ( w, r ) == firstword ( s ) ) ; Hope Tutorial Page 16 The qualified expression is parenthesised so it only applies to the expression after the else, otherwise we'll evaluate "firstword" recursivly as long as the sentence is non-empty, even if it starts with a blank. This version of the function produces: firstword ( "Hope springs eternal ..." ) ; ( "Hope","springs eternal ..." ) : ( list ( char ) # list ( char ) ) We can use this to define a function to split the sentence into a list of its individual words: dec wordlist : list ( char ) -> list ( list ( char ) ) ; --- wordlist ( nil ) <= nil ; --- wordlist ( c :: s ) <= if c = ' ' then wordlist( s ) else ( w :: wordlist ( r ) where ( w, r ) == firstword ( c :: s ) ) ; which we can test by typing an application at the terminal: wordlist ( " While there's life there's Hope " ) ; [ "While","there's","life","there's","Hope" ] : list ( list ( char ) ) Review So far we've concentrated on features of Hope that have something in common with traditional languages such as Pascal, but without many of their limitations, such as fixed-size data structures. We've also been introduced to the functional style of programming where programs are no longer recipes for action, but just definitions of data objects. Now we'll introduce features of Hope that lift it onto a much higher level of expressive power, and let us write programs that are not only extremely powerful and concise, but that can be checked for correctness at compile-time and mechanically transformed into more efficient versions. Hope Tutorial Page 17 Making functions more powerful The Hope compiler can spot many common kinds of error by checking the types of all objects in expressions. This is harder than checking at run-time, but more efficient and saves the embarrassment of discovering an error at run-time in a rarely-executed branch of the air traffic control system we just wrote. However, strict type-checking can be a nuisance if we want to perform some operation that doesn't depend on the type of the data. Try writing a Pascal procedure to reverse an array of either 10 integers or 10 characters and you'll see what I mean. Hope avoids this kind of restriction by allowing a function to operate on more than one type of object. We've already used the standard constructors "::" and "nil" to define a "list ( num )", a "list ( char )" and a "list ( list ( char ) )". The standard equality function "=" will compare any two objects of the same type. Functions with this property are called polymorphic. Pascal's built-in functions "abs" and "sqr" and operations like ">" and "=" are polymorphic in a primitive kind of way. We can define our own polymorphic functions in Hope. The function "cat" we defined above will concatenate lists of numbers, but we can use it for lists containing any type of object. To do this we first declare a kind of 'universal type' called a type variable. We use this in the declaration of "cat" where it stands for any actual type: typevar alpha ; infix cat : 8 ; dec cat : list ( alpha ) # list ( alpha ) -> list ( alpha ) ; This says that "cat" has two parameters that are lists and defines a list, but it doesn't say what kind of object is in the list. However, "alpha" always stands for the same type throughout a given declaration, so all the lists must contain the same type of object. The expressions: [ 1,2,3 ] cat [ 4,5,6 ] and "123" cat "456" are correctly-typed applications of "cat" and define a "list ( num )" and a "list ( char )" respectively, while the expression: [ 1,2,3 ] cat "456" Hope Tutorial Page 18 isn't because "alpha" can't be interpreted as two different types. The interpretation of a type variable is local to a declaration so it can have different interpretations in other declarations without confusion. Of course it only makes sense for a function to be polymorphic as long as the equations defining it don't make any assumptions about types. In the case of "cat" the definition uses only "::" and "nil", which are polymorphic themselves. However, a function like "sumlist" uses "+" and can only be used with lists of numbers as parameters. Defining your own data types Tuples and lists are quite powerful, but for more sophisticated applications, we'll need to define our own types. User-defined types make programs clearer and help the type-checker to help the programmer. We introduce a new data type in a data declaration: data vague == yes ++ no ++ maybe ; "data" is a reserved word and "vague" is the name of the new type. "==" is read as 'is defined as' and "++" is read as 'or'. "yes", "no" and "maybe" are the names for the constructor functions of the new type. We can now write function definitions that use these constructors in patterns: dec evade : vague -> vague ; --- evade ( yes ) <= maybe ; --- evade ( maybe ) <= no ; The constructors can be parameterised with any type of object, including the type that's being defined. We can define types like lists, whose objects are of unlimited size using this kind of recursive definition. As an example, here's a user-defined binary tree that can contain numbers as its leaves: data tree == empty ++ tip ( num ) ++ node ( tree # tree ) ; Hope Tutorial Page 19 There are three constructors. "empty" has no parameters and defines a tree with nothing in it. "tip" defines a tree in terms of a single num, and "node" defines a tree in terms of two other trees. Here's a typical tree: . / \ / \ ___/ \___ ________/ \________ / / \ \ / /\ /\ \ 1 / \ / \ \ / \ / \ 5 2 3 . 4 Here's an example of a function that manipulates trees. It returns the sum of all the numbers contained in one: dec sumtree : tree -> num ; --- sumtree ( empty ) <= 0 ; --- sumtree ( tip ( n ) ) <= n ; --- sumtree ( node ( l, r ) ) <= sumtree ( l ) + sumtree ( r ) ; Unfortunately there's no shorthand for writing tree constants like there is for list constants, so we've got to write them out the long way using constructors. If we want to use "sumtree" to add up all the numbers in the example tree above, we must type in the expression: sumtree ( node ( node ( tip ( 1 ), node ( tip ( 2 ), tip ( 3 ) ) ), node ( node ( empty, tip ( 4 ) ), tip ( 5 ) ) ) ) ; This isn't really a drawback, because programs that manipulate complex data structures like trees will generally define them using other functions. However, it's very useful to be able to type any kind of constant data structure at the terminal when we're checking out an individual function like "sumtree". When we want to test a Pascal program piecemeal, we usually have to write elaborate test harnesses or stubs to generate test data. Hope Tutorial Page 20 Making data more abstract The identifier "list" isn't really a Hope data type. It's called a type constructor and must be parameterised with an actual type before it represents one. We did this every time we declared a "list ( num )" or a "list ( char )". The parameter can also be a user-defined type, as with a "list ( tree )" or even a type variable as in "list ( alpha )", which defines a polymorphic data type. Constructing new data types like this is a compile-time operation by the way, and you shouldn't confuse it with constructing new data values, which is a run-time operation. You can define your own polymorphic data types. Here's a version of the binary tree we defined earlier that can have any type of value in its leaves: data tree ( alpha ) == empty ++ tip ( alpha ) ++ node ( tree ( alpha ) # tree ( alpha ) ) ; Once again, "alpha" is taken to be the same type throughout one instance of a tree. If it's a number, then all references to "tree ( alpha )" are taken as references to "tree ( num )". We can define polymorphic functions that operate on trees containing any type of object, because tree constructors are now polymorphic. Here's a function to 'flatten' a binary tree into a list of the same type of object: dec flatten : tree ( alpha ) -> list ( alpha ) ; --- flatten ( empty ) <= nil ; --- flatten ( tip ( x ) ) <= x :: nil ; --- flatten ( node ( x, y ) ) <= flatten ( x ) <> flatten ( y ) ; Hope Tutorial Page 21 We can demonstrate it on various kinds of tree: flatten( node ( tip ( 1 ), node ( tip ( 2 ), tip ( 3 ) ) ) ) ; [ 1, 2, 3 ] : list ( num ) flatten( node ( tip ( "one" ), node ( tip ( "two" ), tip ( "three" ) ) ) ) ; [ "one","two","three" ] : list ( list ( char ) ) flatten( node ( tip ( tip ( 'a' ) ), node ( tip ( empty ), tip ( node ( tip ( 'c' ), empty ) ) ) ) ) ; [ tip ( 'a' ),empty,node ( tip ( 'c' ), empty) ] : list ( tree ( char ) ) Notice how the type-checker may need to go through several levels of data types to deduce the type of the result. Hope Tutorial Page 22 Even more concise programs The importance of polymorphic types and functions is that they let us write shorter, clearer programs. It's similar to the way Pascal procedures let us use the same code to operate on different data values, but much more powerful. We can write a single Hope function to reverse a list of numbers or characters, where we'd need to write two identical Pascal subroutines to reverse an array of integers and an array of characters. We can use polymorphic functions whenever we're concerned only with the arrangement of the objects in a data structure and not with their values. Sometimes, we'll want to apply some function to the primitive data items in the structure. Here's a function that uses a second function "square" to define a "list (num)" whose elements are the squares of another "list (num)": dec square : num -> num ; --- square ( n ) <= n * n ; dec squarelist : list ( num ) -> list ( num ) ; --- squarelist ( nil ) <= nil ; --- squarelist ( n :: l ) <= square ( n ) :: squarelist ( l ) ; Every time we write a function to process every element of a list, we'll write something almost identical to "squarelist". Here's a function to define a list of factorials: dec fact : num -> num ; --- fact ( 0 ) <= 1 ; --- fact ( succ ( n ) ) <= succ ( n ) * fact ( n ) ; dec factlist : list ( num ) -> list ( num ) ; --- factlist ( nil ) <= nil ; --- factlist ( n :: l ) <= fact ( n ) :: factlist ( l ) ; "factlist" has exactly the same 'shape' as "squarelist", it just applies "fact" instead of "square" and then applies itself recursively. Values that differ between applications are usually supplied as actual parameters. Hope treats functions as data objects, so we can do this in a perfectly natural way. A function that can take another function as an actual parameter is called a higher-order function. When we declare it we must give the type of formal parameter standing for the function in the usual way. The declaration of "fact" tells us that it's: num -> num Hope Tutorial Page 23 Read this as 'a function mapping numbers to numbers'. Now let's see how we can use this idea to write "factlist" and "squarelist" as a single higher- order function. The new function needs two parameters, the original list, and the function that's applied inside it. Its declaration will be: dec alllist : list ( num ) # ( num -> num ) -> list ( num ) ; The 'shape' of "alllist" will be the same as "factlist" and "squarelist", but the function we apply to each element of the list will be the formal parameter: --- alllist ( nil, f ) <= nil ; --- alllist ( n :: l, f ) <= f ( n ) :: alllist ( l, f ) ; We use "alllist" like this: alllist ( [ 2,4,6 ], square ) ; [ 4,16,36 ] : list ( num ) alllist ( [ 2,4,6 ], fact ) ; [ 2,24,720 ] : list ( num ) Notice that there's no argument list after "square" or "fact" in the application of "alllist", so this construction won't be confused with functional composition. "fact( 3 )" represents a function application, but "fact" by itself represents the unevaluated function. Higher-order functions can also be polymorphic. We can use this idea to write a more powerful version of "alllist" that will apply an arbitrary function to every element of a list of objects of arbitrary type. This version of the function is usually known as "map": typevar alpha, beta ; dec map : list ( alpha ) # ( alpha -> beta ) -> list ( beta ) ; --- map ( nil, f ) <= nil ; --- map ( n :: l, f ) <= f ( n ) :: map ( l, f ) ; The definition now uses two type variables "alpha" and "beta". Each one represents the same actual type throughout one instance of "map", but the two types can be different. This means we can use any function that maps alphas to betas to generate a list of betas from any list of alphas. Hope Tutorial Page 24 The actual types aren't restricted to scalars, which makes "map" rather more powerful than we might realise at first sight. Suppose we've got a suitably polymorphic function that finds the length of a list: typevar gamma ; dec length : list ( gamma ) -> num ; --- length ( nil ) <= 0 ; --- length ( n :: l ) <= 1 + length ( l ) ; length ( [ 2,4,6,8 ] ) + length ( "cat" ) ; 7 : num We can use "map" to apply "length" to every element of a list of words defined by "wordlist": map ( wordlist ( "The form remains, the function never dies" ), length ) [ 3,4,8,3,8,5,4 ] : list ( num ) ; In this example "alpha" is taken to be a "list ( char )" and "beta" to be a num, so the type of the function must be "( list ( char ) -> num )". "length" fits the bill if "gamma" is taken to be a character. Hope Tutorial Page 25 Common patterns of recursion "map" is powerful because it sums up a pattern of recursion that turns up frequently in Hope programs. We can see another common pattern in the function "length" used above. Here's another example of the same pattern: dec sum : list ( num ) -> num ; --- sum ( nil ) <= 0 ; --- sum ( n :: l ) <= n + sum ( l ) ; The underlying pattern consists of processing each element in the list and accumulating a single value that forms the result. In "sum", each element contributes its value to the final result. In "length" the contribution is always "1" irrespective of the type or value of the element, but the pattern is identical. Functions that display this pattern are of type: ( list ( alpha ) -> beta ) In the function definition, the equation for a non-empty list parameter will specify an operation whose result is a "beta". This is "+" in the case of "length" and "sum". One argument of the operation will be a list element and the other will be defined by a recursive call, so the type of the operation needs to be: ( alpha # beta -> beta ) This operation differs between applications, so it will be supplied as a parameter. Finally we need a parameter of type "beta" to specify the base case result. The final version of the function is usually known as "reduce". In the following definition, the symbol "!" introduces a comment, which finishes with another "!" or with a newline: dec reduce : list ( alpha ) # ! the input list ! ( alpha # beta -> beta ) # ! the reduction operation ! beta ! the base case result ! -> beta ; ! the result type ! --- reduce ( nil, f, b ) <= b ; --- reduce ( n :: l, f, b ) <= f ( n, reduce ( l, f, b ) ) ; Hope Tutorial Page 26 To use "reduce" as a replacement for "sum" we'll need to supply the standard function "+" as an actual parameter. We can do this if we prefix it with the symbol nonop to tell the compiler we don't want to use it as an infix operator: reduce ( [ 1,2,3 ], nonop +, 0 ) ; 6 : num When we use "reduce" as a replacement for "length", we're not interested in the first argument of the reduction operation because we always add "1" whatever the list element is. This function ignores its first argument: dec addone : alpha # num -> num ; --- addone ( _ , n ) <= n + 1 ; We use "_" to represent any argument we don't want to refer to. reduce ( "a map they could all understand", addone, 0 ) ; 31 : num Like "map", "reduce" is much more powerful than it first appears because the reduction function needn't define a scalar. Here's a candidate that inserts an object into an ordered list of the same kind of object: dec insert : alpha # list ( alpha ) -> list ( alpha ) ; --- insert ( i, nil ) <= i :: nil ; --- insert ( i, h :: t ) <= if i < h then i :: ( h :: t ) else h :: insert ( i, t ) ; Hope Tutorial Page 27 Actually this isn't strictly polymorphic as its declaration suggests, because it uses the built-in function "<", which is only defined over numbers and characters, but it shows the kind of thing we can do. When we use it to reduce a list of characters: reduce ( "All sorts and conditions of men", insert, nil ) ; " Aacddefiillmnnnnoooorssstt" : list ( char ) we can see that it actually sorts them. The sorting method (insertion sort) isn't very efficient, but the example shows something of the power of higher-order functions and of "reduce" in particular. It's even possible to use "reduce" to get the effect of "map", but that's left as an exercise for the reader as they say. Of course "map" and "reduce" only work on "list ( alpha )" and we'll need to provide different versions for our own structured data types. This is the preferred style of Hope programming, because it makes programs largely independent of the 'shape' of the data structures they use. Here's an alternative kind of binary tree that holds data at its nodes rather than its tips, and a reduce function for it: data tree ( alpha ) == empty ++ node ( tree ( alpha ) # alpha # tree ( alpha ) ) ; dec redtree : tree ( alpha ) # ( alpha # beta -> beta ) # beta -> beta ; --- redtree ( empty, f, b ) <= b ; --- redtree ( node ( l, v, r ), f, b ) <= redtree ( l, f, f ( v, redtree ( r, f, b ) ) ) ; We can use this kind of tree to define a more efficient sort. An ordered binary tree has the property that all the objects in its left subtree logically precede the node object and all those in its right subtree are equal to the node object or logically succeed it. We can build an ordered tree if we have a function to insert new objects into an already-ordered tree, such as: dec instree : alpha # tree ( alpha ) -> tree ( alpha ) ; --- instree ( i, empty ) <= node ( empty, i, empty ) ; --- instree ( i, node ( l, v, r ) ) <= if i < v then node ( instree ( i, l ), v, r ) else node ( l, v, instree ( i, r ) ) ; Hope Tutorial Page 28 We can sort a list by converting its elements into an ordered tree using "instree", then flattening the tree back into a list. This is very easy to specify using the two kinds of reduction we've defined: dec sort : list ( alpha ) -> list ( alpha ) ; --- sort ( l ) <= redtree( reduce ( l, instree, empty ), nonop ::, nil ) sort ( "Mad dogs and Englishmen" ) ; " EMaadddegghilmnnnoss" : list ( char ) Anonymous functions When we used "map" and "reduce", we had to define extra functions like "fact" and "square" to pass in as paramteters. This is a nuisance if we don't need them anywhere else in the program and especially if they're trivial, like "sum" or "addone". For on-the-spot use in cases like this, we can use an anonymous function called a lambda-expression. Here's a lambda-expression corresponding to "sum": lambda ( x, y ) => x + y The symbol "lambda" introduces the function and "x" and "y" are its formal parameters. The expression "x + y" is the function definition. The part after "lambda" is just a recursion equation without the "---" and with "=>" instead of "<=". Here's another lambda-expression used as the actual parameter of "reduce": reduce ( [ "toe","tac","tic" ], lambda ( a, b ) => b <> a, nil ) ; "tictactoe" : list ( char ) There can be more than one recursion equation in the lambda- expression. They're separated from each other by the symbol "|" and pattern-matching is used to select the appropriate one. Here's an example that uses pattern-matching in a lambda-expression to avoid division by zero when the function it defines is executed: map ( [ 1,0,2,0,3 ], lambda ( 0 ) => 0 | ( succ ( n ) ) => 100 div succ ( n ) ) ; [ 100,0,50,0,33 ] : list ( num ) Hope Tutorial Page 29 Functions that create new functions As we've seen, Hope functions possess 'full rights' and can be passed as actual parameters like any data object. It'll be no surprise to learn that we can return a function as the result of another function. The result can be a named function or an anonymous function defined by a lambda-expression. Here's a simple example: dec makestep : num -> ( num -> num ) ; --- makestep ( i ) <= lambda ( x ) => i + x ; makestep ( 3 ) ; lambda ( x ) => 3 + x : num -> num As we can see from trying "makestep", its result is an anonymous function that adds a fixed quantity to its single argument. The size of the increment was specified as an actual parameter to "makestep" when the new function was created, and has become 'bound in' to its definition. If we try the new function, we'll see that it really does add "3" to its actual parameter: makestep ( 3 ) ( 10 ) ; 13 : num There are two applications here. First we apply "makestep" to "3", then the resulting anonymous function is applied to "10". Finally, here's a function that has functions as both actual parameter and result: dec twice : ( alpha -> alpha ) -> ( alpha -> alpha ) ; --- twice ( f ) <= lambda ( x ) => f ( f ( x ) ) ; "twice" defines a new function that has a single argument and some other function "f" bound into its definition. The new function has the same type as "f". We can see its effect using a simple function like "square": twice ( square ) ; lambda ( x ) => square( square ( x ) ) : num -> num twice ( square ) ( 3 ) ; 81 : num Hope Tutorial Page 30 The new function applies the bound-in function to its argument twice. We can even bind in "twice" itself, generating a new function that behaves like "twice" except that the function eventually bound in will be applied four times: twice ( twice ) ; lambda ( x ) => twice ( twice ( x ) ) : ( alpha -> alpha ) -> ( alpha -> alpha ) twice ( twice ) ( square ) ( 3 ) ; 43046721 : num Hope Tutorial Page 31 In conclusion In this article you've been introduced to the ideas of functional programming through one of the new generation of functional languages. You saw how a Hope program is just a series of functions that are regarded as definitions of parts of a data structure - the 'results' of the program - and how the powerful idea of higher-order functions allows us to capture many common program patterns in a single function. Some of these ideas will already be familiar to users of LISP, but they appear in a purer form in Hope, because there are no mechanisms for updating data structures like LISP's SETQ and RPLACA or for specifying the order of evaluation like GO and PROG. Unlike LISP programs, Hope programs are free from side-effects and possess the mathematical property of referential transparency. You also saw features that are primitive or lacking in LISP and in most imperative languages. The data declaration lets you define complex data types without worrying about how they're represented and pattern- matching lets you decompose them, so you can use abstract data types directly without writing access procedures and without the need to invent lots of new names. The typing mechanism lets the compiler check that you're using data objects in a correct and consistent way, while the idea of polymorphic types stops the checking from being too restrictive and lets you define common data 'shapes' with a single function. Higher-order functions and polymorphic types allow us to write programs that are very concise. Programmers are more productive and their programs are easier to understand and to reason about. The property of referential transparency improves our ability to reason about programs still further and makes it possible to transform them mechanically into programs that are still provably correct, but more efficient in their use of space or time. Finally, referential transparency keeps the meaning of Hope programs independent of the order they're evaluated in, making them ideal for parallel evaluation on suitable machines. You'll be seeing a lot more of Hope and languages like it in the future. Hope Tutorial Page 32